#pragma once
#ifndef GRAFOCIUDAD_CPP
#define GRAFOCIUDAD_CPP

#include "GrafoCiudad.h"
#include "FuncionHashCuidad.h"
#include <limits>


GrafoCiudad::GrafoCiudad(nat largo, Puntero<Comparador<Puntero<ICiudad>>> comparadorCiudades)
{
	Puntero<ILista<Puntero<Conexion>>> lista = new ListaSimple<Puntero<Conexion>>();
		
	this->matriz = Matriz<Puntero<ListaSimple<Puntero<Conexion>>>>(largo, largo);
	
	for(int i=0;i<largo;i++)
	{
		for(int j=0;j<largo;j++)
		{
			this->matriz[i][j] = new ListaSimple<Puntero<Conexion>>();
		}
	}

	this->posiciones = new TablaHash<Puntero<ICiudad>,int>(comparadorCiudades, new FuncionHashCiudad(), largo);
	this->vertices = Array<Puntero<ICiudad>>(largo);
	this->tope = 0;
	this->cantArcos = 0;
	this->cantVertices = 0;
	this->largo = largo;
	
	this->matrizAux = Matriz<Puntero<Conexion>>(largo, largo);
	this->initMatrizAux();
	this->matrizCaminos = Matriz<bool>(largo, largo);
	this->InitMatrizCaminos();
}

void GrafoCiudad::AgregarVertice(const Puntero<ICiudad>& ciudad)
{
	this->vertices[this->tope] = ciudad;
	this->posiciones->Insertar(ciudad,this->tope);
	this->tope++;
	this->cantVertices++;
}

bool GrafoCiudad::ExisteVertice(const Puntero<ICiudad>& ciudad) const
{
	return this->posiciones->EstaDefinido(ciudad);
}


void GrafoCiudad::AgregarArco(const Puntero<ICiudad>& ciudad1, const Puntero<ICiudad>& ciudad2, const Puntero<Conexion>& arco)
{
	if(this->posiciones->EstaDefinido(ciudad1) && this->posiciones->EstaDefinido(ciudad2))
	{
		int posO = this->posiciones->Recuperar(ciudad1);
		int posD = this->posiciones->Recuperar(ciudad2);

		Puntero<ListaSimple<Puntero<Conexion>>> conx = this->matriz[posO][posD];
		
		//Simplemente inserto la conexion al final de la lista para ese nodo
		conx->InsertarAlFinal(arco);

		this->actualizarMatrizAux(posO, posD, arco);

		this->cantArcos++;
	}
}

int GrafoCiudad::CantidadVertices() const
{
	return this->cantVertices;
}

int GrafoCiudad::CantidadArcos() const
{
	return this->cantArcos;
}

bool GrafoCiudad::EstaLleno() const
{
	return this->largo == this->tope;
}
bool GrafoCiudad::EstaVacio() const
{
	return this->tope==0;
}


const Puntero<Conexion>& GrafoCiudad::ObtenerArcoAux(const Puntero<ICiudad>& ciudad1, const Puntero<ICiudad>& ciudad2) const
{
	int pos = this->posiciones->Recuperar(ciudad1);
	int pos2 = this->posiciones->Recuperar(ciudad2);

	return this->matrizAux[pos][pos2];
}


void GrafoCiudad::ActualizarMatrizCaminos()
{
	for(nat i = 0; i<matrizCaminos.Largo; i++)
	{
		for(nat j = 0; j<matrizCaminos.Largo; j++)
		{
			Puntero<ListaSimple<Puntero<Conexion>>> conx = this->matriz[i][j];
			if (!this->matriz[i][j]->EsVacia())
			matrizCaminos[i][j] = true;
		}
	}

	for(nat k = 0; k<matrizCaminos.Largo; k++)
	{
		for(nat i = 0; i<matrizCaminos.Largo; i++)
		{
			for(nat j = 0; j<matrizCaminos.Largo; j++)
			{
				matrizCaminos[i][j] |= matrizCaminos[i][k] && matrizCaminos[k][j];
			}
			
		}
	}
}

bool GrafoCiudad::ExisteCamino(const Puntero<ICiudad>& ciudadO, const Puntero<ICiudad>& ciudadD) const
{
	int posO = this->posiciones->Recuperar(ciudadO);
	int posD = this->posiciones->Recuperar(ciudadD);

	return matrizCaminos[posO][posD];
}

void GrafoCiudad::ReccoridoMasBaratoConIter(const Puntero<ListaSimple<Puntero<Ciudad>>> listaIter){

	Iterador<Puntero<Ciudad>> iter = listaIter->ObtenerIterador();
	while(iter.HayElemento()){
		Puntero<Ciudad> actual = iter.ElementoActual();
		iter.Avanzar();
		Puntero<Ciudad> primerDestino = iter.ElementoActual();

		int nodoOrigen = this->posiciones->Recuperar(actual);
		int nodoDestino = this->posiciones->Recuperar(primerDestino);

		this->Dijkstra(nodoOrigen,Avion);

		bool existeSolucion = false;
		bool existeCamino = this->ExisteCamino(nodoDestino);

		int costoTotal;
		int cantTramos;
		Array<Puntero<ICiudad>> ciudadesRecorrido;


		iter.Avanzar();
	}



}

Puntero<Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>> GrafoCiudad::RecorridoMasBarato(const Puntero<ICiudad> &ciudadO, const Puntero<ICiudad> &ciudadD)
{

	int nodoOrigen = this->posiciones->Recuperar(ciudadO);
	int nodoDestino = this->posiciones->Recuperar(ciudadD);

	this->Dijkstra(nodoOrigen,Avion);

	bool existeSolucion = false;
	bool existeCamino = this->ExisteCamino(nodoDestino);

	int costoTotal;
	int cantTramos;
	Array<Puntero<ICiudad>> ciudadesRecorrido;

	if(existeCamino)
	{
		costoTotal = this->ObtenerCostoDijkstra(nodoDestino);

		cantTramos = this->CantidadDeTramos(nodoOrigen,nodoDestino);

		ciudadesRecorrido = this->ObtenerCiudadesCaminoMasCorto(nodoOrigen,nodoDestino,cantTramos+1);

		existeSolucion = true;
	}

	if(!existeSolucion)
	{
		Puntero<Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>> retorno = new Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>();
		retorno->AsignarDato1(ERROR);
		retorno->AsignarDato2(0);
		retorno->AsignarDato3(Omnibus);
		retorno->AsignarDato4(NULL);

		return retorno;
	}else
	{
		Puntero<Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>> retorno = new Tupla<TipoRetorno,int, TipoTransporte, Iterador<pCiudad>>();
		retorno->AsignarDato1(OK);
		retorno->AsignarDato2(costoTotal);
		retorno->AsignarDato3(Omnibus);
		retorno->AsignarDato4(ciudadesRecorrido.ObtenerIterador());

		return retorno;
	}


}


#endif